package demo13;

/**
 * 二分查找相关题
 */
public class BinaryFind {
    //1.二分查找（最基础版本）
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        while(left <= right) {
            mid = (left + right) / 2;
            if(nums[mid] > target) {
                right = mid - 1;
            }else if(nums[mid] < target) {
                left = mid + 1;
            }else {
                return mid;
            }
        }
        return -1;
    }
    //2.在排序数组中查找元素的第一个和最后一个位置（也就是寻找左右节点）
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[] { -1, -1 };
        if(nums.length == 0) {
            return ret;
        }
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        // 寻找左端点
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums[left] == target) {
            ret[0] = left;
        }

        // 寻找右端点
        left = 0;
        right = nums.length - 1;
        while (left < right) {
            mid = left + (right - left + 1) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;

            }
        }
        if (nums[left] == target) {
            ret[1] = left;
        }
        return ret;
    }
    //3.搜索插入位置（找右节点）
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        while(left < right) {
            mid = left + (right - left + 1) / 2;
            if(nums[mid] > target) {
                right = mid - 1;
            }else {
                left = mid;
            }
        }
        if(nums[left] == target) {
            return left;
        }else {
            return nums[left] < target ? left + 1 : left;
        }
    }
}
